/*************************************************************************
> File Name: arr.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-08-09 09:23:55
> Description: 贪心算法 模拟 每次取出允许的最大值，然后继续循环
************************************************************************/

#include <iostream>

using namespace std;

const pair<int, string> valueSymbols[] = {
    // 人造hash表
    {1000, "M"},
    {900, "CM"},
    {500, "D"},
    {400, "CD"},
    {100, "C"},
    {90, "XC"},
    {50, "L"},
    {40, "XL"},
    {10, "X"},
    {9, "IX"},
    {5, "V"},
    {4, "IV"},
    {1, "I"},
};

class Solution
{
public:
    string intToRoman(int num)
    {
        string roman;
        for (const auto &[value, symbol] : valueSymbols)
        {
            while (num >= value)
            {
                num -= value;
                roman += symbol;
            }
            if (num == 0)
            {
                break;
            }
        }
        return roman;
    }
};

int main(int argc, char const *argv[])
{
    Solution s;
    cout << s.intToRoman(1994) << endl;
    return 0;
}
